//! @file Vector.h
//! @brief 实现stl中vector类的所有接口\n参考:
//!	- <c++ primer> 第四版 18.1.2 allocator类
//!	- <泛型编程与stl> 侯捷译	16.1.1 vector
//!	- http://www.cplusplus.com/reference/stl/vector/ 
//!     - <c++ Templates: The Complete Guide>, Davide Vandevoorde, Nicolai M. Josuttis
#ifndef VECTOR_H
#define VECTOR_H
#include "Allocator.h"
#include "Iterator.h"

class OutOfRange {
};

class LengthError {

};

template <class T>
class VectorIterator : public Iterator<RandomIteratorTag, T>
{
	T * p;
public:
	typedef typename Iterator<RandomIteratorTag, T>::difference_type difference_type;
	VectorIterator() : p(0) {}
	VectorIterator( T * x) : p(x) {}
	VectorIterator(const VectorIterator & b) : p(b.p) {}
	VectorIterator & operator=(const VectorIterator & b) { p = b.p; return *this;}
	bool operator== (const VectorIterator & b) { return (p == b.p); }	
	bool operator!= (const VectorIterator & b) { return !operator==(b); }
	T& operator* () 
	{
		if (p)
			return *p;
		throw OutOfRange();
	}
	T * operator->()
	{
		if (p)
			return p;
		throw OutOfRange();
	}
	VectorIterator& operator++() 
	{
		++p; 
		return *this;
	}
	VectorIterator& operator--()
	{	
		--p;
		return *this;
	}
	VectorIterator operator++(int) 
	{
		VectorIterator tmp(*this);
		operator++();
		return tmp;
	}
	VectorIterator operator--(int)
	{
		VectorIterator tmp(*this);
		operator--();
		return tmp;
	}	
	VectorIterator operator+(int d) const  {return p + d;}
	VectorIterator operator-(int d) const  {return p - d;}
	
	difference_type operator-(const VectorIterator & it) 
	{ return p - it.p; }

	bool operator>(const VectorIterator & rhs) { return p > rhs.p; }
	bool operator<=(const VectorIterator & rhs) { return !operator>(rhs);}
	bool operator<(const VectorIterator & rhs) { return p < rhs.p; }
	bool operator>=(const VectorIterator &  rhs) { return !operator<(rhs); }
		
	
	
};

template <typename T>
class VectorReverseIterator : public Iterator<RandomIteratorTag, T>
{
	T * p;
public:
	typedef typename Iterator<RandomIteratorTag, T>::difference_type difference_type;
	VectorReverseIterator() : p(0) {}
	VectorReverseIterator( T * x) : p(x) {}
	VectorReverseIterator(const VectorReverseIterator & b) : p(b.p) {}
	VectorReverseIterator & operator=(const VectorReverseIterator & b) { p = b.p; return *this;}
	bool operator== (const VectorReverseIterator & b) { return (p == b.p); }	
	bool operator!= (const VectorReverseIterator & b) { return !operator==(b); }
	T& operator* () 
	{
		if (p)
			return *p;
		throw OutOfRange();
	}
	T * operator->()
	{
		if (p)
			return p;
		throw OutOfRange();
	}
	VectorReverseIterator& operator++() 
	{
		--p; 
		return *this;
	}
	VectorReverseIterator& operator--()
	{	
		++p;
		return *this;
	}
	VectorReverseIterator operator++(int) 
	{
		VectorReverseIterator tmp(*this);
		operator++();
		return tmp;
	}
	VectorReverseIterator operator--(int)
	{
		VectorReverseIterator tmp(*this);
		operator--();
		return tmp;
	}	
	VectorReverseIterator operator+(int d) const  {return p - d;}
	VectorReverseIterator operator-(int d) const  {return p + d;}
	
	difference_type operator-(const VectorReverseIterator & it) 
	{ return it.p - p;  }

	bool operator>(const VectorReverseIterator & rhs) { return p < rhs.p; }
	bool operator<=(const VectorReverseIterator & rhs) { return !operator>(rhs);}
	bool operator<(const VectorReverseIterator & rhs) { return p > rhs.p; }
	bool operator>=(const VectorReverseIterator &  rhs) { return !operator<(rhs); }
};



template <typename T, typename Alloc = Allocator<T> > 
class Vector {
public:
	typedef typename Alloc::reference reference;
	typedef typename Alloc::const_reference const_reference;
	typedef typename Alloc::size_type size_type;
	typedef typename Alloc::difference_type difference_type;
	typedef	typename Alloc::value_type value_type;
	typedef typename Alloc::pointer pointer;
	typedef typename Alloc::const_pointer const_pointer;

	typedef	 Alloc	allocator_type;

	typedef VectorIterator<T> iterator;
	typedef const VectorIterator<T>   const_iterator;
	typedef VectorReverseIterator<T> reverse_iterator;
	typedef const VectorReverseIterator<T> const_reverse_iterator;
	

	
	explicit Vector ( const Alloc& = Alloc() ): head(0), first_free(0), tail(0) {}
	explicit Vector ( size_type n, const T& value= T());
	template <class InputIterator>
	Vector ( InputIterator first, InputIterator last);
	Vector ( const Vector<T,Alloc>& x );
	~Vector ()
	{
		T * p = head;
		for (; p != first_free; ++p)
			alloc.destroy(p);
		alloc.deallocate(head, tail - head);
	}

	Vector<T, Alloc>& operator= (const Vector<T, Alloc>& x);

	size_type size() const
	{
		difference_type diff = first_free - head;
		return ((size_type) diff);
	}

	template <typename InputIterator>
	void assign (InputIterator first, InputIterator last);
	void assign (size_type n, const T& u);

	iterator begin ()  { return head;}
	const_iterator begin () const { return head; }
	
	iterator end ()  { return first_free;}
	const_iterator end () const { return first_free; }


      	reverse_iterator rbegin() {  return first_free - 1;}
	const_reverse_iterator rbegin() const { return first_free - 1;}

	reverse_iterator rend() { return head - 1;}
	const_reverse_iterator rend() const  { return head - 1; }

	reference operator[] ( size_type n )
	{
		return *(begin() + n);
	}
	const_reference operator[] ( size_type n ) const
	{
		return *(begin() + n);
	}

	const_reference at ( size_type n ) const
	{
		if (n < size())
			return *(begin() + n);
		throw OutOfRange();
	}

	reference at ( size_type n )
	{
		if (n < size())
			return *(begin() + n);
		throw OutOfRange();
	}
	reference back ( )
	{
		return (*--end());	
	}

	const_reference back ( ) const
	{
		return (*--end());
	}

	reference front ( )
	{
		return (*begin());
	}

	const_reference front ( ) const
	{
		return (*begin());
	}

	void push_back ( const T& x )
	{
		if (first_free == tail)
			reallocate();	
		alloc.construct(first_free++, x);
	}
	size_type capacity () const
	{
		return  (size_type)(tail - head);
	}
	
	size_type max_size () const
	{
		return alloc.max_size();
	}
	
	void resize ( size_type sz, T c = T() );

	void reserve ( size_type n );

	void clear();

	bool empty () const
	{
		return (head == first_free);
	}

	void pop_back()
	{
		alloc.destroy(--first_free);
	}	
	
	iterator insert ( iterator position, const T& x );
	void insert ( iterator position, size_type n, const T& x );
	template <class InputIterator>
	void insert ( iterator position, InputIterator first, InputIterator last );	

	iterator erase ( iterator position );
	iterator erase ( iterator first, iterator last );

	void swap ( vector<T,Alloc>& vec );

	allocator_type get_allocator() const
	{ 
		return alloc;
	}
private:
	Alloc alloc;		//!< 内存分配器

	T * head;		//!< 指向数组的第一个元素
	T * first_free;		//!< 指向第一个空闲的元素
	T * tail;		//!< 指向数组的最后元素的下一个元素

	void reallocate(size_type n = 1);	
	
	//! @brief 内存拷贝函数
	//! @param[out] dest 目标内存
	//! @param[in] src 源内存
	//! @return void * 返回目标内存末地址
	void * memcpy(void * dest, void const * src, size_type n)
	{
		char * p = (char *) dest;
		char const * q = (char *) src;
		for (size_type i = 0; i < n; ++i)
			*p++ = *q++;

		return p;
	}

	//! @brief 逆向内存拷贝函数
	//! @param[out] dest 目标内存
	//！@param[in] src 源内存
	//! @return void * 返回目标内存逆向末地址
	void * resMemCpy(void * dest, void const * src, size_type n)
	{
		char * p = (char *) dest;
		char const * q = (char *) src;
		for (size_type i = 0; i < n; ++i)
			*p-- = *q--;
	
		return p;
	}

	void swap(T * & s1, T * & s2)
	{
		T * tmp = s1;
		s1 = s2;
		s2 = tmp;
	}
};


// reallocate()
// 下面代码来自<c++ primer>第四版 18.1.2 allocator类
template <typename T, typename Alloc>
void Vector<T, Alloc>::reallocate(size_type n)
{
	size_type size = first_free - head;
	size_type newcapacity = 2 * (size > 0  ? size : 1);

	if (newcapacity < n)
		newcapacity = n;
	
	pointer newhead = alloc.allocate(newcapacity);
	alloc.uninitialized_copy(head, first_free, newhead);
	for (pointer p = first_free; p != head; /* empty */)
		alloc.destroy(--p);

	if (head)
		alloc.deallocate(head, tail - head);
	head = newhead;
	first_free = head + size;
	tail = head + newcapacity;	
}


template <typename T, typename Alloc> 
template <typename InputIterator> 
void Vector<T, Alloc>::assign (InputIterator first, InputIterator last)
{
	size_type size = last - first;
	size_type capacity = tail - head;

	for (pointer p = first_free; p != head; /* empty */)
		alloc.destroy(--p);
	if (size > capacity) {
		size_type newcapacity = 2 *  (size > 1 ? size : 1);
		if (head)
			alloc.deallocate(head, capacity);
		head = alloc.allocate(newcapacity);
		tail = head + newcapacity;	
	}
	
	alloc.uninitialized_copy(first, last, head);

	first_free = head + size;
}

template<typename T, typename Alloc>
void Vector<T, Alloc>::assign (size_type n, const T& u)
{
	size_type capacity = tail - head;

	for (pointer p = first_free; p != head; /* empty */)
		alloc.destroy(--p);
	if (n > capacity) {
		size_type newcapacity = 2 *  (n > 1 ? n : 1);
		if (head)
			alloc.deallocate(head, tail - head);
		head = alloc.allocate(newcapacity);
		tail = head + newcapacity;	
	}

	alloc.uninitialized_fill(head, head + n, u);

	first_free = head + n;
}


template<typename T, typename Alloc>
Vector<T, Alloc>::Vector( size_type n, const T& value) : head(0), first_free(0), tail(0)
{
	assign(n , value);
}

template<typename T, typename Alloc>
template <class InputIterator>
Vector<T, Alloc>::Vector ( InputIterator first, InputIterator last): head(0), first_free(0), tail(0)
{
	assign(first, last);
}

template<typename T, typename Alloc>
Vector<T, Alloc>::Vector ( const Vector<T,Alloc>& x ) : head(0), first_free(0), tail(0)
{
	assign(x.begin(), x.end());
}


template<typename T, typename Alloc>
void Vector<T, Alloc>::clear()
{
//	assign((size_type)0, T());
	assign(pointer(0), pointer(0));
}

template<typename T, typename Alloc>
void Vector<T, Alloc>::resize ( size_type sz, T c )
{
	if (sz < size())
	{
		for(; first_free != head + sz; )
			alloc.destroy(--first_free);
	} else if (sz > size())
	{
		reallocate();
		for(; first_free != head + sz; )
			alloc.construct(first_free++, c);
	}
}

template<typename T, typename Alloc>
void Vector<T, Alloc>::reserve ( size_type n )
{
	if (n > max_size())
		throw LengthError();
	else if (n > capacity())
		reallocate(n);
}

template<typename T, typename Alloc>
Vector<T, Alloc>& Vector<T, Alloc>::operator= (const Vector<T, Alloc>& x)
{
	assign(x.begin(), x.end());

	return *this;
}

template<typename T, typename Alloc>
VectorIterator<T> Vector<T,Alloc>::insert ( iterator position, const T& x )
{
	size_type len = position - head;	
	if (size() + 1 > capacity())
		reallocate();	
	resMemCpy(first_free, first_free - 1, (first_free - (head + len)) * sizeof(T));
	alloc.construct(head + len, x);			
	first_free++;

	return (head + len);
}

template<typename T, typename Alloc>
void Vector<T,Alloc>::insert ( iterator position, size_type n, const T& x )
{
	size_type len = position - head;	
	if (size() + n > capacity())
		reallocate();	
	resMemCpy(first_free + (n - 1), first_free - 1, (first_free - (head + len)) * sizeof(T));
	for (size_type i = 0; i < n; ++i)
	alloc.construct(head + len + i, x);			
	first_free += n;
	
}

template<typename T, typename Alloc>
template <class InputIterator>
void Vector<T,Alloc>::insert ( iterator position, InputIterator first, InputIterator last )
{
	size_type n = last - first;
	size_type len = position -head;
	if (size() + n > capacity())
		reallocate();	
	resMemCpy(first_free + (n - 1), first_free - 1, (first_free - (head + len)) * sizeof(T));
	for (size_type i = 0; i < n; ++i)
	alloc.construct(head + len + i, *first++);			
	first_free += n;
}
	
template<typename T, typename Alloc>
typename Vector<T, Alloc>::iterator Vector<T, Alloc>::erase ( iterator position )
{
	alloc.destroy(&*position);
	size_type num = (end() - position) - 1;
	num = num > 0 ? (num * sizeof(T)) : 0;
	if (num > 0)
	{
		memcpy(&*position, &*(position + 1), num );
		first_free--;
	}

	return position;

}

template<typename T, typename Alloc>
typename Vector<T, Alloc>::iterator Vector<T, Alloc>::erase ( iterator first, iterator last )
{
	alloc.destroy(first, last);
	size_type num = (end() - last);
	if (num > 0)
	{
		memcpy(&*first, &*last, num * sizeof(T) );
		first_free = &*first + num;
	}

	return first;
}

template<typename T, typename Alloc>
void Vector<T, Alloc>::swap ( Vector<T,Alloc>& vec )
{
	swap(head, vec.head);
	swap(first_free, vec.first_free);
	swap(tail, vec.tail);
}

// Equal函数模板代码来源: http://www.cplusplus.com/reference/algorithm/equal/
template <class InputIterator1, class InputIterator2>
  bool Equal ( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2 )
{
  while ( first1!=last1 )
  {
    if (*first1 != *first2)   // or: if (!pred(*first1,*first2)), for pred version
      return false;
    ++first1; ++first2;
  }
  return true;
}

// Lexicographical_compare函数模板的代码来源于: http://www.cplusplus.com/reference/algorithm/lexicographical_compare/
template <class InputIterator1, class InputIterator2>
  bool Lexicographical_compare ( InputIterator1 first1, InputIterator1 last1,
                                 InputIterator2 first2, InputIterator2 last2 )
{
  while (first1!=last1)
  {
    if (first2==last2 || *first2<*first1) return false;
    else if (*first1<*first2) return true;
    first1++; first2++;
  }
  return (first2!=last2);
}

template <class T, class Alloc>
  bool operator== ( const vector<T,Alloc>& x, const vector<T,Alloc>& y )
{
	if (x.size() != y.size())
		return false;
	return ( Equal(x.begin(), x.end(), y.begin() ) );
}

template <class T, class Alloc>
  bool operator< ( const vector<T,Alloc>& x, const vector<T,Alloc>& y )
{
	return Lexicographical_compare( x.begin(), x.end(), y.begin(), y.end() );
}

template <class T, class Alloc>
  bool operator!= ( const vector<T,Alloc>& x, const vector<T,Alloc>& y )
{
	return !operator==(x, y);
}

template <class T, class Alloc>
  bool operator> ( const vector<T,Alloc>& x, const vector<T,Alloc>& y )
{
	return operator<(y, x);
}

template <class T, class Alloc>
  bool operator>= ( const vector<T,Alloc>& x, const vector<T,Alloc>& y )
{
	return !operator<(x, y);
}

template <class T, class Alloc>
  bool operator<= ( const vector<T,Alloc>& x, const vector<T,Alloc>& y )
{
	return !operator>(x, y);
}





#endif 
